package william.binarysearch;

/**
 * @author ZhangShenao
 * @date 2024/1/18
 * @description <a href="https://leetcode.cn/problems/find-smallest-letter-greater-than-target/description/">...</a>
 */
public class Leetcode744_寻找比目标字母大的最小字母 {
    /**
     * 利用二分查找思想
     * Step1: 记录当前符合条件的最小索引
     * Step2: 找到数组中间位置的字母,与目标字母进行比较
     * Step3: 如果中间位置的字母 > 目标字母,说明满足条件,则更新索引,同时抛弃右半部分,继续向左侧查找
     * Step4: 如果中间位置的字母 <= 目标字母,不满足条件,则抛弃左半部分,继续向右查找
     * Step5: 查找完成,返回记录的索引
     */
    public char nextGreatestLetter(char[] letters, char target) {
        //边界条件校验
        if (letters == null || letters.length < 2) {
            throw new RuntimeException("Illegal input!!");
        }

        //记录满足条件的索引
        int idx = 0;

        //借助二分查找思想,在数组[L,R]范围内查找目标字母
        int L = 0;
        int R = letters.length - 1;
        while (L <= R) {
            //获取中间位置的字母,与目标字母进行比较
            int mid = L + ((R - L) >> 1);

            if (letters[mid] > target) { //如果中间位置的字母>目标字母,说明满足条件,则更新索引,同时抛弃右半部分,继续向左侧查找
                idx = mid;
                R = mid - 1;
            } else { //否则中间位置的字母<=目标字母,不满足条件,则抛弃左半部分,继续向右查找
                L = mid + 1;
            }
        }

        //查找完成,返回记录的索引处的字母
        return letters[idx];
    }
}
